package com.chapter4.graph.undirect;

import java.util.Stack;

import com.chapter1.basic.queue.Queue;

/** 
 * @ClassName: BreadthFirstSearch 
 * @Description: BFS广度优先搜索
 * 
 * 应用：最短路径
 * 
 * @author minjun minjun@bw30.com
 * @date 2015-2-25 下午10:20:31 
 *  
 */
public class BreadthFirstSearch {

	//是否访问过该节点
	private boolean[] marked;
	
	//从哪个位置到达这个节点的
	private int[] edgeTo;
	
	//起始点
	private final int s;
	
	public BreadthFirstSearch(Graph g,int s){
		this.s=s;
		marked=new boolean[g.V()];
		edgeTo=new int[g.V()];
		bfs(g,s);
	}

	/** 
	* @Title: bfs 
	* @Description: 广度优先搜索
	* @param @param g
	* @param @param v 设定文件 
	* @return void    返回类型 
	* @throws 
	*/ 
	private void bfs(Graph g, int v) {
		//自定义队列实现
		Queue<Integer> queue=new Queue<Integer>();
		queue.offer(v);
		//标记
		marked[v]=true;
		//轮询队列
		while(!queue.isEmpty()){
			v=queue.poll();
			//将所有的相连节点添加到队列
			for(int m:g.adj(v)){
				if(!marked[m]){
					queue.offer(m);
					//v->m
					edgeTo[m]=v;
					//标记
					marked[m]=true;
				}
			}
		}
	}
	
	/**
	 * 
	* @Title: hasPathTo 
	* @Description: 是否有可达路径 
	* @param @param v
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	/**
	 * 
	* @Title: pathTo 
	* @Description: 获取路径 
	* @param @param v
	* @param @return    设定文件 
	* @return Iterable<Integer>    返回类型 
	* @throws
	 */
	public Iterable<Integer> pathTo(int v){
		if(!marked[v]) throw new RuntimeException("到"+v+"没有可达路径");
		Stack<Integer> path=new Stack<Integer>();
		//循环查找上一个路径节点
		for(int i=v;i!=s;i=edgeTo[i]){
			path.push(i);
		}
		path.push(s);
		return path;
	}
}
